package temp;

import util.MathUtil;

import java.util.Arrays;

/**
 * 快排
 * 1.0 取最后一个数做比较 <=区域放左边，>区域放右边，最后交换大于区域和最后一个数
 * 2.0 取最后一个数做比较 <区域放左边，>区域放右边，=区域放中间，最后交换大于区域和最后一个数
 * 3.0 随机取最后一个数和最后一个数做交换，然后调用2.0(因为随机，所以时间复杂度为 N * logN )
 */
public class QuickSorted {
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    public static void process(int[] arr, int l, int r) {
        if (l < r) {
            int randomIndex = l + (int) (Math.random() * (r - l + 1));
            MathUtil.swap(arr, randomIndex, r);
            int[] partition = quick(arr, l, r);
            process(arr, l, partition[0] - 1);
            process(arr, partition[1] + 1, r);
        }
    }

    private static int[] quick(int[] arr, int l, int r) {
        int less = l - 1;
        int more = r;
        int num = arr[r];
        while (l < more) {
            if (arr[l] < num) {
                MathUtil.swap(arr, ++less, l++);
            } else if (arr[l] == num) {
                l++;
            } else {
                MathUtil.swap(arr, l, --more);
            }
        }
//        MathUtil.swap(arr, l, r);
        MathUtil.swap(arr, more, r);
        return new int[]{less + 1, more};
    }

    public static void main(String[] args) {
        int[] arr = {3, 8, 4, 3, 0, 6, 4, 2, 1, 9, 5, 8, 6, 4, 2, 3, 4, 6, 0, 5, 8, 8, 6};
        quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
